package dp.多少种方案;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 解码方法91.java
 * @createTime 2024年03月01日 14:13:00
 */
public class 解码方法91 {
	/*
   重复子问题
   定义函数dp(i)表示字符串前i个字符，映射的方法为dp[i].
   位置i的映射方案，因为最多两位,所以需要看i和i-1位置的值
   xy
   (1)x=0,y=0   dp[i]=0
   (2)x=0,y!=0  dp[i]=dp[i-1]
   (3)x!=0,y=0,xy<26 dp[i]=dp[i-2]
   (4)x!=0,y=0,xy>26  dp[i]=0
   (4)x!=0,y!=0,xy<26 dp[i]=dp[i-1]+dp[i-2]
   (5)x!=0,y!=0,xy>26 dp[i]=dp[i-1]

	baseCase:
	dp[0]=1;定义为1是因为dp[i-2]可能存在访问dp[0]的情况，这种情况设置为1
	dp[1]= 看字符串的第一个是不是0;
	边界：
	如果长度为1，直接返回dp[1]
	*/
	public  static int numDecodings(String s) {
		int length = s.length();
		int[] dp = new int[length + 1];
		dp[0] = 1;
		dp[1] = s.charAt(0) == '0' ? 0 : 1;
		if (length < 2) {
			return dp[length];
		}
		char[] chars = s.toCharArray();
		//从2开始,因为dp长度大于字符串长度，所以取值都需要向前推1，也就是dp[i]应该是num[i-1]
		for (int i = 2; i <= length; i++) {
			int num = (chars[i - 2] - '0') * 10 + (chars[i - 1] - '0');
			if (chars[i - 1] == '0' && chars[i - 2] == '0') {
				return 0;
			} else if (chars[i - 1] == '0' && chars[i - 2] != '0') {
				dp[i] = dp[i - 1];
			} else if (chars[i - 1] != '0' && chars[i - 2] == '0') {
				if (num > 26) {
					return 0;
				} else {
					dp[i] = dp[i - 2];
				}
			} else if (chars[i - 1] != '0' && chars[i - 2] != '0') {
				if (num > 26) {
					dp[i] = dp[i - 1];
				} else {
					dp[i] = dp[i - 1] + dp[i - 2];
				}
			}
		}
		return dp[length];
	}

	public static void main(String[] args) {
		System.out.println(numDecodings("12"));
	}

}
